% 在本地编译时，采用XeLaTeX编译，pdfLaTeX可能编译失败

\documentclass[11pt]{article}
\usepackage{geometry}
\geometry{left=2.0cm,right=2.0cm,top=2.5cm,bottom=2.5cm}

\usepackage{ctex}
\usepackage{comment}
\usepackage{booktabs}
\usepackage{graphicx}
\usepackage{diagbox}
\usepackage{amsmath,amsfonts,graphicx,amssymb,bm,amsthm}
\usepackage{algorithm,algorithmicx}
\usepackage[noend]{algpseudocode}
\usepackage{fancyhdr}
\usepackage{tikz}
\usepackage{graphicx}
\usetikzlibrary{arrows,automata}
\usepackage{hyperref}
%以下是对latex插入代码块的头文件内容
\usepackage{listings}
\usepackage{color}

\definecolor{dkgreen}{rgb}{0,0.6,0}
\definecolor{gray}{rgb}{0.5,0.5,0.5}
\definecolor{mauve}{rgb}{0.58,0,0.82}

\lstset{frame=tb,
  language=Python,
  aboveskip=3mm,
  belowskip=3mm,
  showstringspaces=false,
  columns=flexible,
  basicstyle={\small\ttfamily},
  numbers=none,
  numberstyle=\tiny\color{gray},
  keywordstyle=\color{blue},
  commentstyle=\color{dkgreen},
  stringstyle=\color{mauve},
  breaklines=true,
  breakatwhitespace=true,
  tabsize=3
}
%以上是对latex插入代码块的头文件内容



\setlength{\headheight}{14pt}

\newcounter{counter_exm}\setcounter{counter_exm}{1}
%\newcounter{counter_thm}\setcounter{counter_thm}{1}
%\newcounter{counter_lma}\setcounter{counter_lma}{1}
%\newcounter{counter_dft}\setcounter{counter_dft}{1}
%\newcounter{counter_clm}\setcounter{counter_clm}{1}
%\newcounter{counter_cly}\setcounter{counter_cly}{1}

\newtheorem{theorem}{\hskip 1.7em 定理}
\newtheorem{lemma}[theorem]{\hskip 1.7em 引理}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{claim}[theorem]{\hskip 1.7em 命题}
\newtheorem{corollary}[theorem]{\hskip 1.7em 推论}
\newtheorem{definition}[theorem]{\hskip 1.7em 定义}

\renewcommand{\emph}[1]{\begin{kaishu}#1\end{kaishu}}

\newenvironment{solution}{{\noindent\hskip 2em \bf 解 \quad}}


\renewenvironment{proof}{{\noindent\hskip 2em \bf 证明 \quad}}{\hfill$\qed$\par}
\newenvironment{example}{{\noindent\hskip 2em \bf 例 \arabic{counter_exm}\quad}}{\addtocounter{counter_exm}{1}\par}

\newenvironment{concept}[1]{{\bf #1\quad} \begin{kaishu}} {\end{kaishu}\par}

\newcommand\E{\mathbb{E}}

% 以上是预定义宏等设置,在不熟悉LaTeX的情况下可不作修改.

% TODO: 在此处更改第X讲
\title{算法设计初步第X讲}
\usetikzlibrary{positioning}

\begin{document}

    \pagestyle{fancy}
    \lhead{\kaishu 杭州师范大学}
    \chead{}
    \rhead{\kaishu 2020年秋季学期算法设计初步}

    % TODO: 在此处更改第X讲、授课时间与记录人
    \begin{center}
        {\LARGE \bf 算法设计初步第一次上机作业}\\
    \end{center}
        \begin{kaishu}
            授课时间: 2020年10月13日\quad
            授课教师: 张仁军
            \hfill 提交人: 范吉祥
        \end{kaishu}
    
    %%%%%%%%%%%%%%%%%%%%% Your note starts from here %%%%%%%%%%%%%%%%%%%%%

    \section{作业描述}
    
    \begin{itemize}
        \subsection{题目描述}
        \item 给定一个整数数组 A, 找到一个具有最大和的连续子数组，并返回其最大和. 例如给定数组
        $$[-2,1,-3,4,-1,2,1,-5,4]$$
        最大子数组和是 6, 连续子数组是 $[4,−1,2,1]$
    \end{itemize}
    \section{答案}
    \begin{itemize}
        \subsection{代码部分} 
        \item 尝试使用快排算法进行解决，即先进行从小到大排序，完成排序之后再选出所需要的元素
        \begin{lstlisting}
        def findmax(A,minloc,maxloc):
            if maxloc==minloc:	
                return(minloc, maxloc, A[minloc])#若数组里只有一个元素，则返回该元素
            else:
                mid=(minloc+maxloc)//2 #找出中间位置
                (left_low,left_high,left_sum)=findmax(A,minloc,mid)
                (right_low,right_high,right_sum)=findmax(A,mid+1,maxloc)
                (cross_low,cross_high,cross_sum)=findmid(A,minloc,mid,maxloc)
                if left_sum>=right_sum and left_sum>=cross_sum:
                    return (left_low,left_high,left_sum)
                elif right_sum>=left_sum and right_sum>=cross_sum:
                    return (right_low,right_high,right_sum)
                else:
                    return (cross_low,cross_high,cross_sum)
            \end{lstlisting}
\newpage
        \begin{lstlisting}
        def findmid(A, minloc, midloc, maxloc):
            INF=2000
            left_SUM=-INF 
            temp=0
            min_left=midloc 
            for i in range(midloc,minloc,-1):
                temp=temp+A[i] 
                if temp>left_SUM:
                    left_SUM=temp
                    min_left=i 
            right_SUM=-INF
            temp=0
            max_right=midloc+1
            for j in range(midloc+1,maxloc):
                temp=temp+A[j]
                if temp>right_SUM:
                    right_SUM=temp
                    max_right=j
            return min_left,max_right,left_SUM+right_SUM
        \end{lstlisting}
        \subsection{主要思想}
        \item 采用分治思想，对于数组不断进行分割计算
        \subsection{正确性证明} 
        \item 先将整个数组A分割成两部分，在中点左侧的数组以及在中点右侧的数组，然后不断进行这样的分割，直到数组的长度只有1，在分割的同时，不断计算左侧数组和右侧数组的最大子数组和以及两侧的和，每次计算时返回两侧子数组取到最大时候的索引
        \item 假设我们要求解的问题是一个规模为n的数组，我们可以将这个问题转化为两个规模为$n/2$的子问题，因此我们对于分治求解有一个初始的选择：递归计算对于这两个$n/2$实例的结果，然后再将它们组合起来，这些解的组合需要用到O(n)的时间，于是运行的时间为$$T(n)<=2T(n/2)+cn$$其中c为某一个常数，我们可以得到一个模式，在递归的第j层，总共由$2^j$个子问题，每个的规模为$\frac{n}{2^j}$,因此第j层对于该问题最多贡献cn的时间，因此当对于总层数为$log_2^n$,需要花费$O(nlogn)$的时间
        \item 对于输入的数组，如果最大子序和在两侧，
        \newpage
        \subsection{运行时间分析}
        \item  每次划分都将原问题变成两个子问题，假设k为划分次数，则当$\frac{n}{2^k}\approx1$时，$k=log_2^n$，而且每次计算最大数组和及其索引时，都要花费O(n)的时间，因此该算法的时间复杂度为$O(nlog_2^n)$

       
    \end{itemize}
    


    
    %%%%%%%%%%%%%%%%%%%%%%%%%%%% End %%%%%%%%%%%%%%%%%%%%%%%%%%%%
    
\end{document}